﻿#define  _CRT_SECURE_NO_WARNINGS 1

//  --------------  数组训练-------------------//

// 洛谷    (小鱼比可爱)  找右边比自己大的数有几个
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int n=0;
//	scanf("%d", &n);
//	int a[101] = { 0 };
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	int b[101] = { 0 };
//	int x = 1;
//	for (int i = 1; i < n; i++)
//	{
//		int count = 0;
//		for (int j = 0; j < i; j++)
//		{
//			if (a[j] < a[i])
//			{
//				count++;
//			}
//		}
//		b[x++] = count;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", b[i]);
//	}
//	return 0;
//}

// 英文字符串倒序
//#include <stdio.h>
//#include <string.h>
////#define M  l00
//int main()
//{
//	char a[100]={0};
//	//scanf("%s", a);
//	gets_s(a);
//	int t = 0;
//	int len = strlen(a);
//	//printf("%d\n", len);
//	//printf("%s", a);
//	for (int i = 0; i < len; i++)
//	{
//		if (a[i] == '0')
//		{
//			 t = i;
//			printf("%d\n", t);
//		}
//	}
//	for (int i = t - 2; i >= 0; i--)
//	{
//		printf("%c", a[i]);
//	}
//	return 0;
//}

// 整型倒序(方法一)
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int n = 0;
//	int a[101] = { 0 };
//	for (int i = 0; i < 100; i++)
//	{
//		scanf("%d", &a[i]);
//		n++;
//		if (a[i] == 0)
//		{
//			break;
//		}
//	}
//	for (int i = n - 2; i >= 0; i--)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}
// 方法二
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int n = 0;
//	int x = 0;
//	int a[100] = { 0 };
//	while (scanf("%d", &x) == 1 && x != 0)
//	{
//		a[n++] = x;
//	}
//	for (int i = n - 1; i >= 0; i--)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}
// 

// 笨小猴  （方法一）：自己写的出现错误
//#include <stdio.h>
//#include <string.h>
//int asd(int m)  // 素数
//{
//	if (m == 0 || m == 1)
//	{
//		return 0;
//	}
//	for (int i = 2; i * i <= m; i++)
//	{
//		if (m % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//
////ubuntuubuntuubuntuubuntuubuntuu
////16 5 15 5 5 14 13 4 12 4 4 11 10 3 9 3 3 8 7 2 6 2 2 5 4 1 3 1 1 2 1
////16 1
////No Answer
////15
//// 出现错误     最小的一直会有 1
//int main()
//{
//	char a[101] = { 0 };
//	int b[101] = { 0 };
//	gets_s(a);
//	int len = strlen(a);
//	int x = 0;
//	for (int i = 0; i < len; i++)
//	{
//		int count = 1;
//		for (int j = i + 1; j < len; j++)
//		{
//			if (a[i] == a[j])
//			{
//				 count++;
//			}
//		}
//		b[x++] = count;
//	}
//	//printf("%d\n", x);
//	for (int i = 0; i < x; i++)
//	{
//		printf("%d ", b[i]);
//	}
//	printf("\n");
//	int max = 0;
//	int min = 1e9;
//	for (int i = 0; i < x; i++)
//	{
//		if (max < b[i])
//		{
//			max = b[i];
//		}
//		if (min > b[i])
//		{
//			min = b[i];
//		}
//	}
//	printf("%d %d", max, min);
//	printf("\n");
//	int sum = max - min;
	/*if (asd(sum) == 1)
	{
		printf("Lucky Word\n");
		printf("%d\n", sum);
	}
	else
	{
		printf("No Answer\n");
		printf("%d\n", sum);
	}*/
//	return 0;
//}

// （方法二）
//#include <stdio.h>
//#include <string.h>
//int asd(int m)  //素数
//{
//	if (m == 0 || m == 1)
//	{
//		return 0;
//	}
//	for (int i = 2; i * i <= m; i++)
//	{
//		if (m % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int main()
//{
//	char a[101] = { 0 };
//	int b[27] = { 0 };
//	gets_s(a);  //输入字符串
//	int len = strlen(a);
//	for (int i = 0; i < len; i++)
//	{
//		b[a[i] - 'a']++;   // 进行字符个数的统计
//	}
//	int maxx = 0;
//	int minn = 1e9;
//	for (int i = 0; i < 26; i++)//比较大小
//	{
//		if (maxx < b[i])
//		{
//			maxx = b[i];
//		}
//		if (b[i] != 0 && b[i] < minn)
//		{
//			minn = b[i];
//		}
//	}
//	int sum = maxx - minn;
//	if (asd(sum) == 1)
//	{
//		printf("Lucky Word\n");
//		printf("%d\n", sum);
//	}
//	else
//	{
//		printf("No Answer\n");
//		printf("%d\n", sum);
//	}
//	return 0;
//}

//一个数字是奇数就*3+1，是偶数就/2，最终回回到1
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int a[1000] = { n };
//	int x = 1;
//	while (n != 1)
//	{
//		if (n % 2 == 0)
//		{
//			a[x] = n / 2;
//			n = n / 2;
//			x++;
//		}
//		else
//		{
//			a[x] = (n * 3) + 1;
//			n = (n * 3) + 1;
//			x++;
//		}
//	}
//	
//	for (int i = x-1; i >=0; i--)
//	{
//		printf("%d ", a[i]);
//	
//	return 0;
//}

//校门外的树   
// 首先全部遍历为1 ，再施工区域的树赋值为 0 ，在统计 1 的个数即可
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int l, m;
//	int a[10010] = { 0 };
//	scanf("%d %d", &l, &m);
//	int u, v;
//	for (int i = 0; i <= l; i++)
//	{
//		a[i] = 1;
//	}
//	for (int i = 0; i < m; i++)
//	{
//		scanf("%d %d", &u, &v);
//		for (int j = u; j <= v; j++)
//		{
//			a[j] = 0;
//		}
//	}
//	int sum = 0;
//	for (int i = 0; i <=l; i++)
//	{
//		if (a[i] == 1)
//		{
//			sum++;
//		}
//	}
//	printf("%d\n", sum);
//	return 0;
//}

// 中彩票
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int a[7] = { 0 };
//	int b[7] = { 0 };
//	int c[7] = { 0 };
//	for (int i = 0; i < 7; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	while (n)
//	{
//		for (int i = 0; i < 7; i++)
//		{
//			scanf("%d", &b[i]);
//		}
//		int sum = 0;
//		for (int i = 0; i < 7; i++)
//		{
//			for (int j = 0; j < 7; j++)
//			{
//				if (a[i] == b[j])
//				{
//					sum++;
//				}
//			}
//		}
//		c[7 - sum]++;
//		n--;
//	}
//	for (int i = 0; i < 7; i++)
//	{
//		printf("%d ", c[i]);
//	}
//	return 0;
//}
// 
// 找出最大数
//#include<stdio.h>
//typedef long long ll;
//int main()
//{
//	ll x;
//	ll n = 0;
//	ll a[100001] = { 0 };
//	while (scanf("%lld", &x) == 1 && x != -1)
//	{
//		a[n++] = x;
//	}
//	ll maxx = -1e7;
//	for (ll i = 0; i < n; i++)
//	{
//		if (maxx < a[i])
//		{
//			maxx = a[i];
//		}
//	}
//	printf("%lld\n", maxx);
//	return 0;
//}
// 
// 
//幻方 二维数组 每一个列，每一行，两个对角线相加都相同
//若 (K−1) 在第一行但不在最后一列，则将 K 填在最后一行， (K−1) 所在列的右一列；
//若 (K−1) 在最后一列但不在第一行，则将 K 填在第一列， (K−1) 所在行的上一行；
//若 (K−1) 在第一行最后一列，则将 K 填在 (K−1) 的正下方；
//若 (K−1) 既不在第一行，也不在最后一列，如果(K−1) 的右上方还未填数
//则将 K 填在(K−1) 的右上方，否则将 K 填在 (K−1) 的正下方。

//上车人数 （按照系数计算）
//#include "iostream"
//using namespace std;
//int main()
//{
//
//    int a, n, m, b;             // a 为始发站人数，n 为车站个数，m为终点站人数，b为第几个车站
//    int x;                     // x 为第二站上车和下车的人数
//    cin >> a >> n >> m >> b;
//    int f[1001] = { 1,1,2 };   // a 的系数
//    int F[1001] = { 0,0,0 };   // x 的系数
//    int s1 = 0, s2 = 0;
//    for (int i = 3; i < n - 1; i++)
//    {
//        f[i] = f[i - 1] + f[i - 2] - 1;           //根据上述规律求出每站 a 的系数
//        F[i] = F[i - 1] + F[i - 2] + 1;           //根据上述规律求出每站 x 的系数
//    }
//    x = (m - f[n - 2] * a) / F[n - 2];              //求出第二站的人数
//    int sum = f[b - 1] * a + F[b - 1] * x;     //求出第 b 站开出时车上的人数
//    cout << sum << endl;
//    return 0;
//}

//（穷举法计算）
//#include <stdio.h>
//#include <math.h>
//
//int main() {
//    int a = 0, n = 0, m = 0, x = 0;
//    scanf("%d %d %d %d", &a, &n, &m, &x);
//    int siteNumber[n + 1];//每一站车上的人数，第0站丢弃不用，从第1站开始，每一个数据元素存储到达该站时汽车上的人数
//    siteNumber[0] = 0;//第0号元素丢弃不用
//    siteNumber[1] = siteNumber[2] = a;//第1站和第2站车上都是a人
//
//    int onPerson[n + 1];//每一站的上车人数
//    onPerson[0] = 0;//同样将第0号元素丢弃不用
//    onPerson[1] = a;//第一站上了a人
//
//    int downPerson[n + 1];//每一站的下车人数
//    downPerson[0] = 0;//同样将第0号元素丢弃不用
//    downPerson[1] = 0;//第1站只有人上车，没有人下车
//
//    for (int i = 1; i < n + 1; ++i) {
//        /*
//         * 既然第二站没说上车、下车多少人，不妨就从1个人开始循环遍历，
//         * 看看第二站到底上多少人才能满足n-1站是m个人，
//         * 注意最后一站是只下人，不上人，在第n-1站时就已经达到了m人
//         * */
//        onPerson[2] = i;
//        downPerson[2] = i;
//
//        //从第三站开始符合规律，即每一站上车人数等于前两站上车人数，下车人数等于上一站上车人数
//        for (int j = 3; j <= n - 1; ++j) {
//            onPerson[j] = onPerson[j - 1] + onPerson[j - 2];
//            downPerson[j] = onPerson[j - 1];
//
//            //计算当前车里的总人数 = 前一站车子上的人数+本站上车人数-本站下车人数
//            siteNumber[j] = siteNumber[j - 1] + onPerson[j] - downPerson[j];
//        }
//
//        //如果第n-1站的人数等于m，那就结束循环，同时输出第x站的人数
//        if (siteNumber[n - 1] == m) {
//            printf("%d", siteNumber[x]);
//            break;
//        }
//
//    }
// return 0;
//}

// 力扣---189.轮转数组
// 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
// 输入：1 2 3 4 5 6 7   3
// 输出：5 6 7 1 2 3 4

//#include <math.h>
//#include <iostream>
//#include <stdio.h>
//#include <math.h>
//#include <algorithm>
//using namespace std;
//void reverse(int* nums, int begin, int end)
//{
//	while (begin < end)
//	{
//		int tmp = nums[begin];
//		nums[begin] = nums[end];
//		nums[end] = tmp;
//
//		++begin;
//		--end;
//	}
//}
//// 三趟逆置倒的思路
//void rotate(int* nums, int numsSize, int k) {
//	if (k > numsSize)
//	{
//		k %= numsSize;
//	}
//	reverse(nums, 0, numsSize - 1);
//	reverse(nums, 0, k - 1);
//	reverse(nums, k, numsSize - 1);
//}
//int main()
//{
//	int a[10] = { 0 };
//	for (int i = 0; i < 7; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	int k = 0;
//	scanf("%d", &k);
//	rotate(a, 7, k);
//	for (int i = 0; i < 7; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}


// CSDN-----每日一题------最长递增序列  (100分)
// 输入 6
// 5 2 3 8 1 9
// 输出：3
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <math.h>
//int solution(int n, int *arr) 
//{
//	int result = 0;
//	int count = 0;
//	for (int i = 0; i < n; i++)
//	{
//		count++;
//		if (arr[i] > arr[i + 1])
//		{
//			count = 0;
//		}
//		if (count > result)
//		{
//			result = count;
//		}
//	}
//	return result+1;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int* arr;
//	arr = (int*)malloc(n * sizeof(int));  // 开辟一个动态数组
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int result = solution(n, arr);
//	printf("%d", result);
//	return 0;
//}

// CSDN-----每日一图------奇偶排序 (未懂)
// 奇数在前，偶数在后
// 方法一：指针做法
//#include<stdlib.h>
//#include<stdio.h>
//void move(int* arr, int sz)
//{
//	int left = 0;
//	int right = sz - 1;
//
//	while (left < right)
//	{
//		//先从前面找
//		while ((left < right) && (arr[left] % 2 != 0))
//		{
//			left++;
//		}//从后面找
//		while ((left < right) && (arr[right] % 2 == 0))
//		{
//			right--;
//		}
//		//就不用判断大小了，避免乱序运行不了
//		int tmp = arr[right];
//		arr[right] = arr[left];
//		arr[left] = tmp;
//
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int* a;
//	a = (int*)malloc(n * sizeof(int));
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	move(a, n - 1);
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}

// 方二：qsort()方法
//#include <stdio.h>
//#include <stdlib.h>
//#include <ctype.h>
//#include <math.h>
//int cmp(const void* a, const void* b)
//{
//	return *(int*)a - *(int*)b;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int* a;
//	int m = 0;
//	int c = n-1;
//	a = (int*)malloc(n * sizeof(int));
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &a[i]);
//		if (a[i] % 2 == 0)
//		{
//			a[c--] = a[i];  //偶数在右边
//		}
//		else
//		{
//			a[m++] = a[i];
//		}
//	}
//	qsort(a, m, sizeof(a[0]), cmp);
//	qsort(a + m, n-m-1, sizeof(a[0]), cmp);
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}


//力扣 ---     26   ----- 数组去重（双指针）
//int removeDuplicates(int* nums, int numsSize)
//{
//    int scr = 0, des = 0;
//    while (scr < numsSize)
//    {
//        if (nums[scr] == nums[des])
//        {
//            scr++;
//        }
//        else
//        {
//            nums[++des] = nums[scr++];
//
//        }
//    }
//    return des + 1;
//}

// 力扣------88-----合并两个有序数组
//int cmp_int(const void* a, const void* b)
//{
//	return *(int*)a - *(int*)b;    //升序
//	//return * (int * )b-* (int *)a;    //降序
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//	/*if(nums2Size==0)
//	{
//		return;
//	}*/
//	for (int i = 0; i < n; i++)
//	{
//		nums1[i + m] = nums2[i];
//	}
//	qsort(nums1, nums1Size, sizeof(int), cmp_int);
//}


// C网 ---------- 1518 ----- 寻找三位数
// 题目描述：
// 将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成
// 1：2：3的比例，试求出所有满足条件的三个三位数。
// 例如：三个三位数192，384，576满足以上条件。

// 方法（一） ：C语言：排序 + sprintf()输入
// sprintf() 解释：把对应的内容写入到指定字符串中；其实这个函数和printf函数一样的只是printf把 数据写到屏幕上，
// 而sprintf函数把数据写入指定指定字符串中；
// 就是比printf多了一个参数，其他参数和printf一样；
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//#include <math.h>
//int cmp_char(const void* a, const void* b)
//{
//	return *(char*)a - *(char*)b;  //升序
//	//return *(char*)a - *(char*)b;  //降序
//}
//int main()
//{
//	char a[10] = "123456789";
//	char s[10] = { 0 };
//	// 假设为 abc:def:ghi  ,其中abc最小为123 ghi最大为987  987/3=329
//	// 所以 ghi 除以3 就是abc 的最大值 进行遍历即可
//	for (int i = 123; i <= 329; i++)
//	{
//		sprintf(s, "%d%d%d", i, 2 * i, i * 3);
//		qsort(s, 9, sizeof(s[0]), cmp_char);  //字符串升序排序
//		if (strcmp(s, a) == 0)  // 满足所有的数字是由 1~9组成
//		{
//			printf("%d %d %d\n", i, 2 * i, 3 * i);
//		}
//	}
//	return 0;
//}

//方法（二）：C++ +STL库（next_permutation）
// next_permutation(数组名，数组名+长度)
//#include <stdio.h>
//#include <algorithm>
//#include <stdlib.h>
//#include <iostream>
//using namespace std;
//typedef long long ll;
//int main()
//{
//	int a[10] = { 0 };
//	for (int i = 1; i <= 9; i++)
//	{
//		a[i] = i; // 将 1，2，3，4，5，6，7，8，9放入数组 
//	}
//	ll x, y, z;  //  三组数据
//	do
//	{
//		x = a[1] * 100 + a[2] * 10 + a[3];
//		y = a[4] * 100 + a[5] * 10 + a[6];
//		z = a[7] * 100 + a[8] * 10 + a[9];
//		if (2 * x == y * 1 && 3 * y == 2 * z)  //避免误差
//		{
//			cout << x << " " << y << " " << z << endl;
//		}
//	} while (next_permutation(a + 1, a + 10)); //进行全排列
//	return 0;
//}

// C网--------- 1440---- 蓝桥杯：带分数 -----//
// 100  可以表示为带分数的形式：100 = 3 + 69258 / 714。
// 还可以表示为：100 = 82 + 3546 / 197。
// 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
// 类似这样的带分数，100  有  11  种表示法。

// 思路： 1.整数位数最大只能为7     2.分子位数必须大于分母位数    3.分母位数不能没有
//       4.最后判断 整数 + 分子 / 分母 == N && 分子 % 分母 == 0  缺一不可！！
//       5.还一个很坑的地方，求分子分母位数时，最好控制分母的位数，因为有上限为9，便于控制

// 方法（一）
//#include <stdio.h>
//#include <iostream>
//#include <stdlib.h>
//#include <string.h>
//#include <math.h>
//#include <algorithm>
//typedef long long ll;
//using namespace std;
//int len(int n)   //求整数的位数
//{
//	int sum = 0;
//	while (n)
//	{
//		sum++;
//		n = n / 10;
//	}
//	return sum;
//}
//int asd(int x, int y, int* a)  // 将 a数组中 i位数 到 j位数 转变成整数
//{
//	int sum = 0;
//	for (int i = x; i <= y; i++)
//	{
//		sum = sum * 10 + a[i];
//	}
//	return sum;
//}
//int main()
//{
//	int a[10] = { 0 };
//	for (int i = 1; i < 10; i++)
//	{
//		a[i] = i;
//	}
//	ll x;
//	scanf("%lld", &x);
//	ll count = 0;
//	do
//	{
//		for (int i= 1; i <=len(x); i++)   // 整数不能超过 x 的位数 ，且不能超过7 位（留两位，分子分母各一位）
//		{
//			int inter = asd(1, i, a);
//			for (int j = i + 1; j <= 8; j++)  // 整数后面给分数 （分子+分母）   j<=8 是保证最后一位 留给分母
//			{
//				int fz = asd(i + 1, j, a);    // 整数后面是分子，最少一位，最多的情况是只留一位给分母
//				int fm = asd(j + 1, 9, a);    // 分子后面是分母，最少的情况是一个
//				if (inter + (fz / fm) == x && (fz % fm) == 0)
//				{
//					count++;
//				}
//			}
//		}
//
//	} while (next_permutation(a + 1, a + 10));
//	printf("%lld\n", count);
//	return 0;
//}

// 方法二
//#include<iostream>
//#include<algorithm> 
//using namespace std;
//int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
//bool book[10];
//int total = 0, N;
////把获取的数组起终点下标转化成数 
//int getNum(int x, int y) 
//{
//	int num = 0;
//	for (int i = x; i <= y; i++) 
//	{
//		num = num * 10 + a[i];
//	}
//	return num;
//}
////判断是否符合等式要求
//void judge(int *a) 
//{
//	int i, j;
//	//整数位的范围是1~7 
//	for (i = 1; i <= 7; i++) 
//	{
//		//先求整数
//		int integer = getNum(1, i);
//		//控制分母范围较好，因为控制分子的话，分母的范围会被降低！！ 
//		for (j = i+1; j <= 8; j++) 
//		{
//			int fz = getNum(i + 1, j); //分子必须留一位给分母
//			int fm = getNum(j+1, 9);
//			if (integer + fz / fm == N && (fz % fm) == 0)
//			{
//				total++;
//			}
//		}
//	}
//}
//int main() 
//{
//	cin >> N;
//	do {
//		judge(a);
//	} while (next_permutation(a + 1, a + 10));
//	cout << total << endl;
//	return 0;
//}

// C网-------名校训练-------第K极值
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//#include <math.h>
//int prime(int m)
//{
//	if (m <= 1)
//	{
//		return 0;
//	}
//	for (int i = 2; i <= (int)sqrt(m); i++)
//	{
//		if (m % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int cmp_int(const void *a,const void *b)
//{
//	return *(int*)a - *(int*)b;
//}
//int main()
//{
//	int z[10001] = { 0 };
//	int N, k;
//	scanf("%d%d", &N, &k);
//	for (int i = 0; i < N; i++)
//	{
//		scanf("%d", &z[i]);
//	}
//	qsort(z, N, sizeof(z[0]), cmp_int);
//	int sum = z[N - k] - z[k-1];
//	if (prime(sum) == 0)
//	{
//		printf("NO\n");
//		printf("%d\n", sum);
//	}
//	else
//	{
//		printf("YES\n");
//		printf("%d\n", sum);
//	}
//	return 0;
//}


// C网-------名校训练--------谁拿的奖最多(100分)
//#include <stdio.h>
//#include <string.h>
//#include <stdlib.h>
//#include <math.h>
//typedef struct money
//{
//	char name[21];  // 名字 
//	int x;       // 期末成绩
//	int y;       // 班级评议成绩
//	char b;      // 是否是学生干部
//	char c;      // 是否西部省份学生
//	int z;       // 发表论文个数
//}student;
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	student arr[101];
//	int sum = 0;
//	int sun = 0;
//	int max = -1;
//	int t = 0;
//	for (int i = 0; i < n; i++)
//	{
//		sun = 0;
//		scanf("%s %d %d %c %c %d", &arr[i].name, &arr[i].x, &arr[i].y, &arr[i].b, &arr[i].c, &arr[i].z);
//		if (arr[i].x > 80 && arr[i].z >= 1)
//		{
//			sun = sun + 8000;
//		}
//		if (arr[i].x > 85 && arr[i].y > 80)
//		{
//			sun = sun + 4000;
//		}
//		if (arr[i].x > 90)
//		{
//			sun = sun + 2000;
//		}
//		if (arr[i].x > 85 && arr[i].c == 'Y')
//		{
//			sun = sun + 1000;
//		}
//		if (arr[i].y > 80 && arr[i].b == 'Y')
//		{
//			sun = sun + 850;
//		}
//		if (max < sun)
//		{
//			max = sun;
//			t = i;
//		}
//		sum = sum + sun;
//	}
//	printf("%s\n", arr[t].name);
//	printf("%d\n", max);
//	printf("%d\n", sum);
//	return 0;
//}


//C网----------名校训练---------贝西的训练（100分）
//#include <stdio.h>
//#include <stdlib.h>
//#include <math.h>
//#include <string.h>
//typedef long long ll;
//int main()
//{
//	ll M, T, U, F, D;
//	scanf("%lld %lld %lld %lld %lld", &M, &T, &U, &F, &D);
//	char z;
//	ll time = 0;
//	ll sum = 0;
//	char a[100001] = { 0 };
//	ll b = 0;
//	for (int i = 1; i <= T; i++)
//	{
//		getchar();    // 注意去掉缓冲区的空格.
//		scanf("%c", &z);
//		//getchar();
//		a[b++] = z;
//	}
//	ll c = 0;
//	while (time <= M)
//	{
//		if (a[c] == 'u'|| a[c] == 'd')
//		{
//			time = time + U + D;
//		}
//		else if (a[c] == 'f')
//		{
//			time = time + 2 * F;
//		}
//		if (time > M)
//		{
//			break;
//		}
//		sum++;
//		c++;
//	}
//	printf("%lld\n", sum);
//	return 0;
//}


// C网------------蓝桥杯----------2006 寻找奇整数(100).
// 注意是否在序列里面
// return 1 表示结束这个函数（循环、判断）
//#include<stdio.h>
//int main() 
//{
//    int arr[] = { 3,7,5,13,25,45,78,23,8,33,9,19,28,41,50 };
//    int k = 1, n;
//    scanf("%d", &n);
//    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
//    {
//        if (arr[i] != n) 
//        {
//            k++;
//        }
//        else 
//        {
//            break;
//        }
//    }
//    if (n % 2 == 0 || k == 16) 
//    {
//        printf("Error");
//    }
//    else 
//    {
//        printf("%d", k);
//    }
//    return 0;
//}

// 判断一个序列是否为另外一个序列的子序列
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N], b[N];
//int main() {
//    int n, m;
//    cin >> n >> m;
//    //读入序列
//    for (int i = 0; i < n; i++)
//        cin >> a[i];
//    for (int i = 0; i < m; i++)
//        cin >> b[i];
//    int i = 0, j = 0;//双指针
//    while (i < n && j < m) {
//        if (a[i] == b[j])
//        {
//            i++;//如果相等
//            j = -1;
//        }
//        j++;
//    }
//    if (i == n)
//        cout << "Yes";//如果i移动到了边界外就说名全部匹配上
//    else 
//        cout << "No" << endl;
//    return 0;
//}

//#include <iostream>
//using namespace std;
//const int N = 1000000 + 10;
//int a[N] = { 0 };
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 2; j <= n; j++)
//		{
//			if (i % j == 0)
//			{
//				if (a[i] == 0)
//					a[i]++;
//				else if (a[i] == 1)
//					a[i]--;
//			}
//		}
//	}
//	int flag = 0;
//	int sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		if (a[i] == 0)
//		{
//			if (flag == 0)
//			{
//				flag = 1;
//				cout << i;
//			}
//			else 
//				cout << " " << i;
//		}
//	}
//	return 0;
//}


//#include <string.h>
//#include<stdio.h>
//#include<stdlib.h>
//const int N = 1000000 + 10;
//int a[N] = { 0 };
//int main(int argc, char* argv[])
//{
//	int i, j, k = 0;
//	int n;
//	scanf("%d", &n);
//	for (i = 1; i <= n; i++)
//	{
//		a[i] = 1;     //初始化，全部朝上
//	}
//		//从第二张开始翻可以和从第三张及以后开始一起处理是因为初始条件是牌全部向上，第二张要翻可以用a[j] = a[j] * (-1)处理
//	for (i = 2; i <= n; i++)  //从第二张开始。。。到n张   i表示倍数   j表示要查询的牌
//	{
//		for (j = i; j <= n; j++)  //从第i张开始 查询到最后一张  判断j是否为i的倍数
//		{
//			if (j % i == 0)				//如果是i的倍数，比如从第二张开始 j为i的倍数（此时i=2）的，牌的朝向翻转
//				a[j] = a[j] * (-1);     //乘以负一，等价于牌翻转
//		}
//
//	}
//	for (i = 1; i <= n; i++)
//	{
//		if (a[i] == 1)
//		{
//			k++;
//			printf("%d ", i);
//		}
//	}
//	printf("\n");
//	printf("总共有%d张牌正面朝上\n", k);
//}

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int f[100][100];//状态函数f[i][j]表示第i件物品容量为j最大价值
int v[100];
int w[100];
/*
函数功能：求0-1背包问题的最大价值
函数形参：物品数量和背包容量
函数返回值：返回最大值
*/
int fun(int n, int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (j < w[i])
				f[i][j] = f[i - 1][j];
			else
				f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
		}
	}
	return f[n][m];
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	cout << fun(n, m);
	return 0;
}

